{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Sub Islands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubIslands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计子岛屿"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <code>m x n</code> 的二进制矩阵 <code>grid1</code> 和 <code>grid2</code> ，它们只包含 <code>0</code> （表示水域）和 <code>1</code> （表示陆地）。一个 <strong>岛屿</strong> 是由 <strong>四个方向</strong> （水平或者竖直）上相邻的 <code>1</code> 组成的区域。任何矩阵以外的区域都视为水域。</p>\n",
    "\n",
    "<p>如果 <code>grid2</code> 的一个岛屿，被 <code>grid1</code> 的一个岛屿 <strong>完全</strong> 包含，也就是说 <code>grid2</code> 中该岛屿的每一个格子都被 <code>grid1</code> 中同一个岛屿完全包含，那么我们称 <code>grid2</code> 中的这个岛屿为 <strong>子岛屿</strong> 。</p>\n",
    "\n",
    "<p>请你返回 <code>grid2</code> 中 <strong>子岛屿</strong> 的 <strong>数目</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/10/test1.png\" style=\"width: 493px; height: 205px;\">\n",
    "<pre><b>输入：</b>grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>如上图所示，左边为 grid1 ，右边为 grid2 。\n",
    "grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/03/testcasex2.png\" style=\"width: 491px; height: 201px;\">\n",
    "<pre><b>输入：</b>grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]\n",
    "<b>输出：</b>2 \n",
    "<strong>解释：</strong>如上图所示，左边为 grid1 ，右边为 grid2 。\n",
    "grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid1.length == grid2.length</code></li>\n",
    "\t<li><code>n == grid1[i].length == grid2[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 500</code></li>\n",
    "\t<li><code>grid1[i][j]</code> 和 <code>grid2[i][j]</code> 都要么是 <code>0</code> 要么是 <code>1</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-sub-islands](https://leetcode.cn/problems/count-sub-islands/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-sub-islands](https://leetcode.cn/problems/count-sub-islands/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]]\\n[[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]', '[[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]]\\n[[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "\n",
    "        def bfs(sx: int, sy: int) -> int:\n",
    "            q = deque([(sx, sy)])\n",
    "            grid2[sx][sy] = 0\n",
    "            # 判断岛屿包含的每一个格子是否都在 grid1 中出现了\n",
    "            check = (grid1[sx][sy] == 1)\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and grid2[nx][ny] == 1:\n",
    "                        q.append((nx, ny))\n",
    "                        grid2[nx][ny] = 0\n",
    "                        if grid1[nx][ny] != 1:\n",
    "                            check = False\n",
    "            \n",
    "            return int(check)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    ans += bfs(i, j)\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-sub-islands/solutions/836393/tong-ji-zi-dao-yu-by-leetcode-solution-x32x/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Deque\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        q: Deque[Tuple[int, int]] = deque()\n",
    "        res = 0\n",
    "\n",
    "        def bfs() -> bool:\n",
    "            flag = True\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                if grid1[i][j] == 0:\n",
    "                    flag = False\n",
    "                for cx, cy in direction:\n",
    "                    nx, ny = i + cx, j + cy\n",
    "                    if (\n",
    "                        0 <= nx < m\n",
    "                        and 0 <= ny < n\n",
    "                        and grid2[nx][ny] == 1\n",
    "                        and not visited[nx][ny]\n",
    "                    ):\n",
    "                        # 在加入队列时，标记为已访问\n",
    "                        visited[nx][ny] = True\n",
    "                        q.append((nx, ny))\n",
    "\n",
    "            return flag\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and not visited[i][j]:\n",
    "                    # 在加入队列时，标记为已访问\n",
    "                    visited[i][j] = True\n",
    "                    q.append((i, j))\n",
    "                    res += bfs()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Deque\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        q: Deque[Tuple[int, int]] = deque()\n",
    "        res = 0\n",
    "\n",
    "        def bfs() -> bool:\n",
    "            flag = True\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                if grid1[i][j] == 0:\n",
    "                    print(i, j)\n",
    "                    flag = False\n",
    "                for cx, cy in direction:\n",
    "                    nx, ny = i + cx, j + cy\n",
    "                    if (\n",
    "                        0 <= nx < m\n",
    "                        and 0 <= ny < n\n",
    "                        and grid2[nx][ny] == 1\n",
    "                        and not visited[nx][ny]\n",
    "                    ):\n",
    "                        # 在加入队列时，标记为已访问\n",
    "                        visited[nx][ny] = True\n",
    "                        q.append((nx, ny))\n",
    "\n",
    "            return flag\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and not visited[i][j]:\n",
    "                    # 在加入队列时，标记为已访问\n",
    "                    visited[i][j] = True\n",
    "                    q.append((i, j))\n",
    "                    res += bfs()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        ans = 0\n",
    "\n",
    "        idx = 2\n",
    "        for i in range(m):\n",
    "            for j  in range(n):\n",
    "                if grid1[i][j] == 1:\n",
    "                    q = deque([(i, j)])\n",
    "                    grid1[i][j] = idx\n",
    "\n",
    "                    while q:\n",
    "                        x, y = q.popleft()\n",
    "                        for dx, dy in pairwise(direction):\n",
    "                            a, b = x + dx, y + dy\n",
    "                            if 0 <= a < m and 0 <= b < n and grid1[a][b] == 1:\n",
    "                                grid1[a][b] = idx\n",
    "                                q.append((a, b))\n",
    "\n",
    "                    idx += 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    s = set([grid1[i][j]])\n",
    "                    q = deque([(i, j)])\n",
    "                    grid2[i][j] = 0\n",
    "\n",
    "                    while q:\n",
    "                        x, y = q.popleft()\n",
    "                        for dx, dy in pairwise(direction):\n",
    "                            a, b = x + dx, y + dy\n",
    "                            if 0 <= a < m and 0 <= b < n and grid2[a][b] == 1:\n",
    "                                grid2[a][b] = 0\n",
    "                                q.append((a, b))\n",
    "                                s.add(grid1[a][b])\n",
    "                    \n",
    "                    if len(s) == 1 and list(s)[0] > 0:\n",
    "                        ans += 1\n",
    "                        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        m=len(grid1)\n",
    "        n=len(grid1[0])\n",
    "        tem=[]\n",
    "        stack=[]\n",
    "        visited=[[0 for _ in range (0,n)] for _ in range (0,m)]\n",
    "        for i in range (0,m):\n",
    "            for j in range (0,n):\n",
    "                \n",
    "                if grid2[i][j]==1 and visited[i][j]==0:\n",
    "                    tem=[]\n",
    "                    stack=[]\n",
    "                    visited[i][j]=1\n",
    "                    tem.append([i,j])\n",
    "                   \n",
    "                    while tem:\n",
    "                        u=tem.pop(0)\n",
    "                        stack.append(u)\n",
    "                        if u[0]>0 and grid2[u[0]-1][u[1]]==1 and visited[u[0]-1][u[1]]==0:\n",
    "                            visited[u[0]-1][u[1]]=1\n",
    "                            tem.append([u[0]-1,u[1]])\n",
    "                        if u[0]<m-1 and grid2[u[0]+1][u[1]]==1 and visited[u[0]+1][u[1]]==0:\n",
    "                            visited[u[0]+1][u[1]]=1\n",
    "                            tem.append([u[0]+1,u[1]])\n",
    "                        if u[1]<n-1 and grid2[u[0]][u[1]+1]==1 and visited[u[0]][u[1]+1]==0:\n",
    "                            visited[u[0]][u[1]+1]=1\n",
    "                            tem.append([u[0],u[1]+1])\n",
    "                        if u[1]>0 and grid2[u[0]][u[1]-1]==1 and visited[u[0]][u[1]-1]==0:\n",
    "                            visited[u[0]][u[1]-1]=1\n",
    "                            tem.append([u[0],u[1]-1])\n",
    "                    flag=0\n",
    "                    for h in stack:\n",
    "                        if grid1[h[0]][h[1]]==0:\n",
    "                            flag=1\n",
    "                            break\n",
    "                    if flag==0:\n",
    "                        ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        # def idx(i, j):\n",
    "        #     return i * n + j\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        def color(mat):\n",
    "            start = 2\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if mat[i][j] == 1:\n",
    "                        mat[i][j] = start\n",
    "                        # vis = set((i, j)) #染色过程已经实现了vis功能\n",
    "                        dq = deque([[i, j]])\n",
    "                        while dq:\n",
    "                            cur_len = len(dq)\n",
    "                            for _ in range(cur_len):\n",
    "                                x, y = dq.popleft()\n",
    "                                for nx, ny in [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]:\n",
    "                                    if valid(nx, ny) and mat[nx][ny] == 1:\n",
    "                                        mat[nx][ny] = start\n",
    "                                        dq.append([nx, ny])\n",
    "                        start += 1\n",
    "            return mat, start - 1\n",
    "        \n",
    "        mat2, start2 = color(grid2)\n",
    "\n",
    "        posi = set(range(2, start2 + 1))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (tar := mat2[i][j]) != 0 and tar in posi and grid1[i][j] == 0:\n",
    "                    posi.remove(tar)\n",
    "                        \n",
    "        return len(posi)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        rows,cols = len(grid1),len(grid1[0])\n",
    "        used   = [[False] * cols for _ in range(rows)]\n",
    "        labels = [[-1]    * cols for _ in range(rows)]\n",
    "        dirs = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        stack = []\n",
    "        res = 0\n",
    "        # mark grid1\n",
    "        cur_label = -1\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid1[r][c] == 0: continue\n",
    "                if labels[r][c] != -1: continue\n",
    "                stack.append((r,c))\n",
    "                cur_label += 1\n",
    "                labels[r][c] = cur_label\n",
    "                while stack:\n",
    "                    pr,pc = stack.pop()\n",
    "                    for dr,dc in dirs:\n",
    "                        if (nr := pr + dr) < 0 or nr >= rows: continue\n",
    "                        if (nc := pc + dc) < 0 or nc >= cols: continue\n",
    "                        if grid1[nr][nc]  ==  0: continue\n",
    "                        if labels[nr][nc] != -1: continue\n",
    "                        labels[nr][nc] = cur_label\n",
    "                        stack.append((nr,nc))\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid2[r][c] == 0: continue\n",
    "                if used[r][c]: continue\n",
    "                stack.append((r,c))\n",
    "                flag = grid1[r][c] == 1\n",
    "                while stack:\n",
    "                    pr,pc = stack.pop()\n",
    "                    if flag and labels[pr][pc] != labels[r][c]: \n",
    "                        flag = False\n",
    "                    for dr,dc in dirs:\n",
    "                        if (nr := pr + dr) < 0 or nr >= rows: continue\n",
    "                        if (nc := pc + dc) < 0 or nc >= cols: continue\n",
    "                        if grid2[nr][nc] == 0: continue\n",
    "                        if used[nr][nc]: continue\n",
    "                        used[nr][nc] = True\n",
    "                        stack.append((nr,nc))\n",
    "                if flag:\n",
    "                    res += 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.parents = [0] * (m * n)\n",
    "        self.ranks = [0] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = i * n + j\n",
    "                self.parents[idx] = idx\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parents[x] != x:\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        if self.ranks[x] < self.ranks[y]:\n",
    "            self.parents[px] = py\n",
    "        elif self.ranks[x] > self.ranks[y]:\n",
    "            self.parents[py] = px\n",
    "        else:\n",
    "            self.parents[py] = px\n",
    "            self.ranks[px] += 1\n",
    "        \n",
    "    \n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        uf = UnionFind(grid1)\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j]:\n",
    "                    idx = i * n + j\n",
    "                    if i < m - 1 and grid1[i + 1][j]:\n",
    "                        uf.union(idx, idx + n)\n",
    "                    if j < n - 1 and grid1[i][j + 1]:\n",
    "                        uf.union(idx, idx + 1)\n",
    "        res = 0\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 0 or visited[i][j]:\n",
    "                    continue\n",
    "                queue = deque([(i, j)])\n",
    "                visited[i][j] = True\n",
    "                pre, flag = -1, 1\n",
    "                while queue:\n",
    "                    x, y = queue.popleft()\n",
    "                    cur = uf.find(x * n + y)\n",
    "                    if grid1[x][y] and (pre == -1 or cur == pre):\n",
    "                        pre = cur\n",
    "                    else:\n",
    "                        flag = 0\n",
    "                    for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid2[nx][ny] == 1 and not visited[nx][ny]:\n",
    "                            queue.append((nx, ny))\n",
    "                            visited[nx][ny] = True\n",
    "                if flag:\n",
    "                    res += 1\n",
    "        return res\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], zi: List[List[int]]) -> int:\n",
    "        rowlen,collen=len(grid1),len(grid1[0])\n",
    "        visited=[[0]*collen for _ in range(rowlen)]\n",
    "        count=0\n",
    "        for i in range(rowlen):\n",
    "            for j in range(collen):\n",
    "                if zi[i][j] == 1 and visited[i][j] ==0:\n",
    "                    root=[(i,j)]\n",
    "                    count+=1\n",
    "                    while root:\n",
    "                        x,y=root.pop()\n",
    "                        if zi[x][y] == 1 and visited[x][y] == 0:\n",
    "                            visited[x][y]=count\n",
    "                            if x >= 1 :root.append((x-1,y))\n",
    "                            if x < rowlen-1:root.append((x+1,y))\n",
    "                            if y >=  1:root.append((x,y-1))\n",
    "                            if y < collen-1:root.append((x,y+1))\n",
    "        bi={i:1 for i in range(1,count+1)}\n",
    "        for i in range(rowlen):\n",
    "            for j in range(collen):\n",
    "                if visited[i][j] != 0:\n",
    "                    if grid1[i][j] == 1 :\n",
    "                        continue\n",
    "                    else:\n",
    "                        bi[visited[i][j]]-=1\n",
    "        return sum([i for i in bi.values() if i == 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        n, m = len(grid1), len(grid1[0])\n",
    "        vis = set()\n",
    "\n",
    "        def bfs(x, y):\n",
    "            q = deque([(x, y)])\n",
    "            vis.add((x, y))\n",
    "            flag = grid1[x][y] == 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if grid1[x][y] == 0:\n",
    "                    flag = False\n",
    "                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in vis and grid2[nx][ny] == 1:\n",
    "                        vis.add((nx, ny))\n",
    "                        q.append((nx, ny))\n",
    "            \n",
    "            return flag\n",
    "\n",
    "        ans = 0\n",
    "        for i, j in product(range(n), range(m)):\n",
    "            if grid2[i][j] == 1 and (i, j ) not in vis:\n",
    "                ans += bfs(i, j)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.father = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, k):\n",
    "        while(self.father[k] != k):\n",
    "            k = self.father[k]\n",
    "        return k\n",
    "\n",
    "    def union(self, i ,j):\n",
    "        fai = self.find(i)\n",
    "        faj = self.find(j)\n",
    "        self.father[faj] = fai\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid2), len(grid2[0])\n",
    "        grid = UnionSet(m*n)\n",
    "        step = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(grid2[i][j] == 1):\n",
    "                    for d in step:\n",
    "                        ni, nj = i + d[0], j + d[1]\n",
    "                        if(ni>=0 and nj >= 0 and ni < m and nj < n):\n",
    "                            if(grid2[ni][nj] == 1):\n",
    "                                grid.union(i*n + j, ni*n + nj)\n",
    "                        else:\n",
    "                            continue\n",
    "        cnt = [0 for i in range(m*n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                fa = grid.find(i*n+j)\n",
    "                if(grid2[i][j] == 1):\n",
    "                    if(cnt[fa]==0):\n",
    "                        cnt[fa] = 1\n",
    "                    if(grid1[i][j] != 1):\n",
    "                        cnt[fa] = -1\n",
    "        for i in cnt:\n",
    "            if(i == 1):\n",
    "                ans += 1\n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        # def idx(i, j):\n",
    "        #     return i * n + j\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        def color(mat):\n",
    "            start = 2\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if mat[i][j] == 1:\n",
    "                        mat[i][j] = start\n",
    "                        # vis = set((i, j)) #染色过程已经实现了vis功能\n",
    "                        dq = deque([[i, j]])\n",
    "                        while dq:\n",
    "                            cur_len = len(dq)\n",
    "                            for _ in range(cur_len):\n",
    "                                x, y = dq.popleft()\n",
    "                                for nx, ny in [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]:\n",
    "                                    if valid(nx, ny) and mat[nx][ny] == 1:\n",
    "                                        mat[nx][ny] = start\n",
    "                                        dq.append([nx, ny])\n",
    "                        start += 1\n",
    "            return mat, start - 1\n",
    "        \n",
    "        mat1, start1 = color(grid1)\n",
    "        mat2, start2 = color(grid2)\n",
    "\n",
    "        posi = set(range(2, start2 + 1))\n",
    "        d, ans = {}, 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j] != 0 and mat2[i][j] in posi:\n",
    "                    tar = mat2[i][j]\n",
    "                    if tar in d:\n",
    "                        pre = d[tar]\n",
    "                        now = mat1[i][j]\n",
    "                        if pre != now:\n",
    "                            posi.remove(tar)\n",
    "                    else:\n",
    "                        if mat1[i][j] != 0:\n",
    "                            d[tar] = mat1[i][j]\n",
    "                        else:\n",
    "                            posi.remove(tar)\n",
    "                        \n",
    "        return len(posi)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self,):\n",
    "        self.visited=[]\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        q=[]\n",
    "        n_row=len(grid2)\n",
    "        n_col=len(grid2[0])\n",
    "\n",
    "        self.visited=[[False for i in range(n_col)]for j in range(n_row)]\n",
    "        ones=[]\n",
    "        for i in range(n_row):\n",
    "            for j in range(n_col):\n",
    "                if grid2[i][j]==1:\n",
    "                    ones.append((i,j))\n",
    "        containCount=0\n",
    "        for one in ones:\n",
    "            if self.visited[one[0]][one[1]]:\n",
    "                continue\n",
    "            q.append((one[0],one[1]))\n",
    "            isContain=True\n",
    "            while q:\n",
    "                cur_node=q.pop(0)\n",
    "                x,y=cur_node\n",
    "                if self.visited[x][y]:\n",
    "                    continue\n",
    "                self.visited[x][y]=True\n",
    "                if grid1[x][y]==0:\n",
    "                    isContain=False\n",
    "                for direct in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                    next_x=x+direct[0]\n",
    "                    next_y=y+direct[1]\n",
    "                    if next_x<0 or next_x>n_row-1 or next_y<0 or next_y>n_col-1:\n",
    "                        continue\n",
    "                    if grid2[next_x][next_y]==1:\n",
    "                        q.append((next_x,next_y))\n",
    "            if isContain:\n",
    "                containCount+=1\n",
    "        return containCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS:\n",
    "    def __init__(self, n):\n",
    "        self.father = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx, rooty = self.find(x), self.find(y)\n",
    "        if rootx == rooty:\n",
    "            return\n",
    "        self.father[rooty] = rootx\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "\n",
    "        ufs = UFS(m * n)    \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]:\n",
    "                    if i > 0 and grid2[i - 1][j]:\n",
    "                        ufs.union(i * n + j, (i - 1) * n + j)\n",
    "                    if j > 0 and grid2[i][j - 1]:\n",
    "                        ufs.union(i * n + j, i * n + j - 1)\n",
    "        \n",
    "        area = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]:\n",
    "                    root = ufs.find(i * n + j)\n",
    "                    if area.get(root, 1):\n",
    "                        area[root] = grid1[i][j]\n",
    "\n",
    "        return sum(area.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        # 并查集\n",
    "        n, m = len(grid1), len(grid1[0])\n",
    "        p = [i for i in range(n * m)]\n",
    "        v = [0] * (n * m)\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        # 合并\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if grid1[x][y] == 1:\n",
    "                    for k in range(4):\n",
    "                        a = x + dx[k]\n",
    "                        b = y + dy[k]\n",
    "                        if a >= 0 and a < n and b >= 0 and b < m and grid1[a][b] == 1:\n",
    "                            idx1 = x * m + y\n",
    "                            idx2 = a * m + b\n",
    "                            p1 = find(idx1)\n",
    "                            p2 = find(idx2)\n",
    "                            if p1 != p2:\n",
    "                                p[p2] = p1\n",
    "        # return p\n",
    "\n",
    "        def check(i, j, pa):\n",
    "            # 检查是否以[i, j] 连通域内的点都属于集合pa\n",
    "            q = deque()\n",
    "            q.append([i, j])\n",
    "            grid2[i][j] = 0\n",
    "            res = True\n",
    "            while len(q):\n",
    "                x, y = q.popleft()\n",
    "                for k in range(4):\n",
    "                    a = x + dx[k]\n",
    "                    b = y + dy[k]\n",
    "                    if a >= 0 and a < n and b >= 0 and b < m and grid2[a][b] == 1:\n",
    "                        q.append([a, b])\n",
    "                        grid2[a][b] = 0\n",
    "                        if find(a * m + b) != pa:\n",
    "                            res = False\n",
    "            return res                    \n",
    "        ans = 0\n",
    "        rr = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] == 1 and grid1[i][j] == 1:\n",
    "                    pa = find(i * m + j)\n",
    "                    if check(i, j, pa):\n",
    "                        rr.append([i, j, pa])\n",
    "                        ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from typing import *\n",
    "from collections import Counter, deque, defaultdict\n",
    "from bisect import *\n",
    "from heapq import heappop, heappush, heapify\n",
    "from functools import lru_cache\n",
    "from itertools import accumulate, product\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        lands2 = []\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            ans = []\n",
    "            ans.append((i, j))\n",
    "            grid2[i][j] = 0\n",
    "            q = [(i, j)]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x, y in tmp:\n",
    "                    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and grid2[nx][ny] == 1:\n",
    "                            grid2[nx][ny] = 0\n",
    "                            ans.append((nx, ny))\n",
    "                            q.append((nx, ny))\n",
    "            return ans\n",
    "        \n",
    "        for i, j in product(range(m), range(n)):\n",
    "            if grid2[i][j] == 1:\n",
    "                lands2.append(dfs(i, j))\n",
    "        \n",
    "        ans = 0\n",
    "        for arr in lands2:\n",
    "            tag = True\n",
    "            for x, y in arr:\n",
    "                if grid1[x][y] == 0:\n",
    "                    tag = False\n",
    "                    break\n",
    "            if tag:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int) -> None:\n",
    "        self.parent = [[(i, j) for j in range(m)] for i in range(n)]\n",
    "        self.is_included = [[True for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "    def find(self, element: Tuple[int]) -> Tuple[int]:\n",
    "        father = self.parent[element[0]][element[1]]\n",
    "        if father != element:\n",
    "            self.parent[element[0]][element[1]] = self.find(father)\n",
    "        return self.parent[element[0]][element[1]]\n",
    "\n",
    "    def merge(self, element_a: Tuple[int], element_b: Tuple[int]) -> Tuple[int]:\n",
    "        root_a, root_b = self.find(element_a), self.find(element_b)\n",
    "        self.parent[root_a[0]][root_a[1]] = root_b\n",
    "        self.is_included[root_b[0]][root_b[1]\n",
    "                                    ] &= self.is_included[root_a[0]][root_a[1]]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        n, m = len(grid1), len(grid1[0])\n",
    "        uf_set = UnionFind(n, m)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] != 1:\n",
    "                    continue\n",
    "                uf_set.is_included[i][j] = grid1[i][j] == 1\n",
    "                if i > 0 and grid2[i - 1][j] == 1:\n",
    "                    uf_set.merge((i, j), (i - 1, j))\n",
    "                if j > 0 and grid2[i][j - 1] == 1:\n",
    "                    uf_set.merge((i, j), (i, j - 1))\n",
    "        counter = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] == 1 and uf_set.parent[i][j] == (i, j) and uf_set.is_included[i][j] == True:\n",
    "                    counter += 1\n",
    "        return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        def count(grid):\n",
    "            c = []\n",
    "            m,n = len(grid), len(grid[0])\n",
    "            def dfs(i,j):\n",
    "                nonlocal  grid, c\n",
    "                s = [(i,j)]\n",
    "                grid[i][j]=0\n",
    "                v = set(s)\n",
    "                flag = 0\n",
    "                if i==0 or i==m-1 or j==0 or j==n-1:\n",
    "                    flag=1\n",
    "                while s:\n",
    "                    x,y = s.pop()\n",
    "                    for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                        if 0<=i<m and 0<=j<n and grid[i][j]==1:\n",
    "                            grid[i][j]=0\n",
    "                            v.add((i,j))\n",
    "                            s.append((i,j))\n",
    "                c.append(v)\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==1:\n",
    "                        dfs(i,j)\n",
    "\n",
    "            return c\n",
    "        a = count(grid2)\n",
    "        res = 0\n",
    "        for i in a:\n",
    "            l = 1\n",
    "            for x,y in i:\n",
    "                if grid1[x][y]==0:\n",
    "                    l=0\n",
    "            res+=l\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        n_row, n_col = len(grid1), len(grid1[0])\n",
    "        res = 0\n",
    "        islands2 = []\n",
    "        q2 = deque([])\n",
    "        for row in range(n_row):\n",
    "            for col in range(n_col):\n",
    "                island2 = set()\n",
    "                if grid2[row][col] == 1:\n",
    "                    q2.append((row, col))\n",
    "                    while q2:\n",
    "                        r_g2, c_g2 = q2.popleft()\n",
    "                        if grid2[r_g2][c_g2] == 1:\n",
    "                            island2.add((r_g2, c_g2))\n",
    "                            grid2[r_g2][c_g2] = 0\n",
    "                        for dr_g2, dc_g2 in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                                r1_g2, c1_g2 = r_g2+dr_g2, c_g2+dc_g2\n",
    "                                if 0 <= r1_g2 < n_row and 0 <= c1_g2 < n_col and grid2[r1_g2][c1_g2] == 1:\n",
    "                                    island2.add((r1_g2, c1_g2))\n",
    "                                    q2.append((r1_g2, c1_g2))\n",
    "                                    grid2[r1_g2][c1_g2] = 0\n",
    "                    if island2:\n",
    "                        islands2.append(island2)\n",
    "        \n",
    "        for i in islands2:\n",
    "            key = True\n",
    "            for x, y in i:\n",
    "                if grid1[x][y] == 0:\n",
    "                    key = False\n",
    "            if key:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        def bfs(matrix):\n",
    "            m, n = len(matrix), len(matrix[0])\n",
    "            dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "            res = []\n",
    "            flag = 2\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if matrix[i][j] == 1:\n",
    "                        matrix[i][j] = flag\n",
    "                        cur = [[i, j]]\n",
    "                        l = [[i, j]]\n",
    "                        while cur:\n",
    "                            ne = []\n",
    "                            for k in cur:\n",
    "                                for x, y in dirs:\n",
    "                                    newx = k[0] + x\n",
    "                                    newy = k[1] + y\n",
    "                                    if 0<=newx<m and 0<=newy<n and matrix[newx][newy]==1:\n",
    "                                        matrix[newx][newy] = flag\n",
    "                                        ne.append([newx, newy])\n",
    "                                        l.append([newx, newy])\n",
    "                            cur = ne\n",
    "                        flag += 1\n",
    "                        res.append(l)\n",
    "            return res\n",
    "        \n",
    "        bfs(grid1)\n",
    "        res = bfs(grid2)\n",
    "        result = 0\n",
    "        for i in range(len(res)):\n",
    "            su = 0\n",
    "            length = len(res[i])\n",
    "            for j in range(length):\n",
    "                if grid1[res[i][j][0]][res[i][j][1]] == 0:\n",
    "                    break\n",
    "                if j == 0:\n",
    "                    flag = grid1[res[i][j][0]][res[i][j][1]]\n",
    "                    su += 1\n",
    "                else:\n",
    "                    if grid1[res[i][j][0]][res[i][j][1]] != flag:\n",
    "                        break\n",
    "                    else:\n",
    "                        su += 1\n",
    "            if su == length:\n",
    "                result += 1\n",
    "        \n",
    "        return result\n",
    "\n",
    "                    \n",
    "                    \n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "                    m = len(grid1)\n",
    "                    n = len(grid1[0])\n",
    "                    \n",
    "                    p1 = [i for i in range(m*n)]\n",
    "                    p2 = [i for i in range(n*m)]\n",
    "                    def find(p,x):\n",
    "                        if p[x] != x:\n",
    "                            p[x] = find(p,p[x])\n",
    "                        return p[x]\n",
    "                    def union(p,x,y):\n",
    "                        x = find(p,x)\n",
    "                        y = find(p,y)\n",
    "                        p[x] = y\n",
    "                    for i in range(m):\n",
    "                        for j in range(n):\n",
    "                            if grid1[i][j] == 0:\n",
    "                                if i and grid1[i-1][j] == 0:\n",
    "                                    union(p1,(i-1)*n+j,i*n+j)\n",
    "                                if j and grid1[i][j-1] == 0:\n",
    "                                    union(p1,i*n+j - 1,i*n+j)\n",
    "                            if grid2[i][j] == 1:\n",
    "                                if j and grid2[i][j-1] == 1:\n",
    "                                    union(p2,i*n+j - 1,i*n+j)\n",
    "                                if i and grid2[i-1][j] == 1:\n",
    "                                    union(p2,(i-1)*n+j,i*n+j)\n",
    "                    vis = set()\n",
    "                    for i in range(m):\n",
    "                        for j in range(n):\n",
    "                            if grid2[i][j] == 1:\n",
    "                                vis.add(find(p2,i*n+j))\n",
    "                    for i in range(m):\n",
    "                        for j in range(n):\n",
    "                            d = find(p1,i * n + j)\n",
    "                            x = d // n;y = d % n\n",
    "                            if grid2[i][j] == 1 and grid1[x][y] == 0:\n",
    "                                t = find(p2,i*n+j)\n",
    "                                if t in vis:\n",
    "                                    vis.remove(t)\n",
    "                    \n",
    "                    return len(vis)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        rows,cols = len(grid1),len(grid1[0])\n",
    "        used   = set()\n",
    "        labels = [[-1]    * cols for _ in range(rows)]\n",
    "        dirs = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        stack = []\n",
    "        res = 0\n",
    "        # mark grid1\n",
    "        cur_label = -1\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid1[r][c] == 0: continue\n",
    "                if labels[r][c] != -1: continue\n",
    "                stack.append((r,c))\n",
    "                cur_label += 1\n",
    "                labels[r][c] = cur_label\n",
    "                while stack:\n",
    "                    pr,pc = stack.pop()\n",
    "                    for dr,dc in dirs:\n",
    "                        if (nr := pr + dr) < 0 or nr >= rows: continue\n",
    "                        if (nc := pc + dc) < 0 or nc >= cols: continue\n",
    "                        if grid1[nr][nc]  ==  0: continue\n",
    "                        if labels[nr][nc] != -1: continue\n",
    "                        labels[nr][nc] = cur_label\n",
    "                        stack.append((nr,nc))\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid2[r][c] == 0: continue\n",
    "                if (r,c) in used: continue\n",
    "                stack.append((r,c))\n",
    "                flag = grid1[r][c] == 1\n",
    "                while stack:\n",
    "                    pr,pc = stack.pop()\n",
    "                    if flag and labels[pr][pc] != labels[r][c]: \n",
    "                        flag = False\n",
    "                    for dr,dc in dirs:\n",
    "                        if (nr := pr + dr) < 0 or nr >= rows: continue\n",
    "                        if (nc := pc + dc) < 0 or nc >= cols: continue\n",
    "                        if grid2[nr][nc] == 0: continue\n",
    "                        if (nr,nc) in used: continue\n",
    "                        used.add((nr,nc))\n",
    "                        stack.append((nr,nc))\n",
    "                if flag:\n",
    "                    res += 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集\n",
    "class union_set:\n",
    "    def __init__(self, n):\n",
    "        self.par = [-1 for _ in range(n)]\n",
    "        self.height = [0 for _ in range(n)]\n",
    "\n",
    "    def find(self, p):\n",
    "        tmp = p\n",
    "        while self.par[p] != -1:\n",
    "            p = self.par[p]\n",
    "        res = p\n",
    "        p = tmp\n",
    "        while self.par[p] != -1:\n",
    "            t = self.par[p]\n",
    "            self.par[p] = res\n",
    "            p = t\n",
    "        return res\n",
    "\n",
    "    def union_(self, x, y):\n",
    "        # print(x, y)\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        # print('after,', x, y)\n",
    "        if x == y:\n",
    "            return\n",
    "\n",
    "        if self.height[x] > self.height[y]:\n",
    "            self.par[y] = x\n",
    "        else:\n",
    "            # print('this function is called')\n",
    "            self.par[x] = y\n",
    "            if self.height[x] == self.height[y]:\n",
    "                self.height[y] += 1\n",
    "\n",
    "        return None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 1:\n",
    "                    grid1[i][j] += grid2[i][j]\n",
    "                if grid1[i][j] == 0:\n",
    "                    grid1[i][j] += -grid2[i][j]\n",
    "        us = union_set(m*n)\n",
    "        dir = [[-1, 0], [0, -1]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 2 or grid1[i][j] == -1:\n",
    "                    for dx, dy in dir:\n",
    "                        nx = i + dx\n",
    "                        ny = j + dy\n",
    "                        if nx < 0 or ny < 0 or nx >= m or ny >= n or grid1[nx][ny] == 1 or grid1[nx][ny] == 0:\n",
    "                            continue\n",
    "                        us.union_(i * n + j, nx * n + ny)\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for i in range(m * n):\n",
    "            p = us.find(i)\n",
    "            x, y = i // n, i % n\n",
    "            if grid1[x][y] == 2 or grid1[x][y] == -1:\n",
    "                d[p].append((i // n, i % n))\n",
    "\n",
    "        res = 0\n",
    "        for k, v in d.items():\n",
    "            f = 1\n",
    "            for x, y in v:\n",
    "                if grid1[x][y] == -1:\n",
    "                    f = 0\n",
    "                    break\n",
    "            res += f\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m , n = len(grid1) , len(grid1[0])\n",
    "        count = [[0] * n for _ in range(m)]\n",
    "        c = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                count[i][j] = c\n",
    "                c+=1\n",
    "        djs = list(range(c))\n",
    "\n",
    "        def find(x:int) -> int :\n",
    "            if djs[x] != x:\n",
    "                djs[x] = find(djs[x])\n",
    "            return djs[x]\n",
    "        def union(x,y) -> None:\n",
    "            djs[find(x)] = find(y)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n and grid2[i][j] == grid2[i][j+1]:\n",
    "                    union(count[i][j],count[i][j+1])\n",
    "                if i+1 < m and grid2[i][j] == grid2[i+1][j]:\n",
    "                    union(count[i][j], count[i+1][j])\n",
    "                if grid2[i][j]==0:\n",
    "                    union(count[i][j], 0)\n",
    "\n",
    "        ansadd = set()\n",
    "        ansminus = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if find(count[i][j]) != find(0) and grid1[i][j] == 1 :\n",
    "                    ansadd.add(find(count[i][j]))\n",
    "                elif find(count[i][j]) != find(0) and grid1[i][j] == 0 :\n",
    "                    ansminus.add(find(count[i][j]))\n",
    "\n",
    "        return len(ansadd-ansminus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        rank_1 = self.countIslands(grid1)\n",
    "        rank_2 = self.countIslands(grid2)\n",
    "\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        \n",
    "        _dict = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rank_2[i*n+j] != -1:\n",
    "                    _dict[rank_2[i*n+j]].append((i, j))\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for k, v in _dict.items():\n",
    "            target = None\n",
    "            flag = True\n",
    "            for x, y in v:\n",
    "                if rank_1[x*n+y] == -1:\n",
    "                    flag = False\n",
    "                    break\n",
    "                else:\n",
    "                    if target is None:\n",
    "                        target = rank_1[x*n+y]\n",
    "                    else:\n",
    "                        if rank_1[x*n+y] != target:\n",
    "                            flag = False\n",
    "                            break\n",
    "            ans += flag\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def countIslands(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ranks = [i*n+j for i in range(m) for j in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if ranks[x] != x:\n",
    "                ranks[x] = find(ranks[x])\n",
    "            return ranks[x]\n",
    "        \n",
    "        def isConnected(x, y):\n",
    "            return find(x) == find(y)\n",
    "        \n",
    "        def union(x, y):\n",
    "            if not isConnected(x, y):\n",
    "                ranks[find(x)] = ranks[find(y)]\n",
    "        \n",
    "        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ranks[i*n+j] = -1\n",
    "                    continue\n",
    "                for _x, _y in directions:\n",
    "                    x, y = i + _x, j + _y\n",
    "                    if x < 0 or x == m or y < 0 or y == n:\n",
    "                        continue\n",
    "                    if grid[x][y] == 0:\n",
    "                        continue\n",
    "                    union(x*n+y, i*n+j)\n",
    "        for i, rank in enumerate(ranks):\n",
    "            if ranks[i] != -1:\n",
    "                find(i)\n",
    "        # print(ranks)\n",
    "        return ranks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        n, m = len(grid1), len(grid1[0])\n",
    "        parents = [[(i, j) for j in range(m)] for i in range(n)]\n",
    "        def find(x):\n",
    "            i, j = x\n",
    "            if parents[i][j] == x: return x\n",
    "            parents[i][j] = find(parents[i][j])\n",
    "            return parents[i][j]\n",
    "        def merge(x, y):\n",
    "            x_, y_ = find(x), find(y)\n",
    "            i, j = y_\n",
    "            parents[i][j] = x_\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] == 0: continue\n",
    "                if i > 0 and grid2[i - 1][j] == 1:\n",
    "                    merge((i - 1, j), (i, j))\n",
    "                if j > 0 and grid2[i][j - 1] == 1:\n",
    "                    merge((i, j - 1), (i, j))\n",
    "        invalid = set()\n",
    "        tot = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] == 0: continue\n",
    "                p = find((i, j))\n",
    "                tot.add(p)\n",
    "                if grid1[i][j] == 0: invalid.add(p)\n",
    "        return len(tot - invalid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind():\n",
    "    def __init__(self,n):\n",
    "        self.parent= list(range(n))\n",
    "        self.size =[1]*n\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.parent[x]==x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union(self,x,y):\n",
    "        rootX= self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX==rootY:\n",
    "            return \n",
    "        self.parent[rootY]= rootX\n",
    "        self.size[rootX]+=self.size[rootY]\n",
    "        \n",
    "    def connected(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "class Solution:\n",
    "    def buildUF(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        u = UnionFind(m*n)\n",
    "        def pos2idx(i,j):\n",
    "            return i*n+j\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    continue \n",
    "                if i+1<m and grid[i+1][j]==1: # 下\n",
    "                    u.union(pos2idx(i,j),pos2idx(i+1,j))\n",
    "                if j+1<n and grid[i][j+1]==1:\n",
    "                    u.union(pos2idx(i,j),pos2idx(i,j+1))\n",
    "        return u\n",
    "\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m,n = len(grid1),len(grid1[0])\n",
    "        u2= self.buildUF(grid2)\n",
    "        cnt = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==0:\n",
    "                    continue \n",
    "                idx = i*n+j\n",
    "                cnt[u2.find(idx)].append((i,j))\n",
    "        ret =0 \n",
    "        for v in cnt.values():\n",
    "            flag = 1\n",
    "            for i,j in v:\n",
    "                if grid1[i][j]!=1:\n",
    "                    flag=0\n",
    "                    break\n",
    "            ret+=flag\n",
    "        return ret \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict, deque\n",
    "dx = [1, 0, -1, 0]\n",
    "dy = [0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid2), len(grid2[0])\n",
    "        q = deque([])\n",
    "        visited = set()\n",
    "        record = defaultdict(list)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and (i, j) not in visited:\n",
    "                    q.append((i, j))\n",
    "                    visited.add((i, j))\n",
    "                    record[len(record)].append((i, j))\n",
    "                    while q:\n",
    "                        node = q.popleft()\n",
    "                        for k in range(4):\n",
    "                            x = node[0] + dx[k]\n",
    "                            y = node[1] + dy[k]\n",
    "                            if self.isvalid(grid2, x, y) and (x, y) not in visited:\n",
    "                                q.append((x, y))\n",
    "                                visited.add((x, y))\n",
    "                                record[len(record) - 1].append((x, y))\n",
    "                                \n",
    "        # 检查每一个岛屿是否是grid1岛屿的子集(即是否都是1-1)\n",
    "        count = 0\n",
    "        for key in record:\n",
    "            is_island = True\n",
    "            for pos in record[key]:\n",
    "                if grid1[pos[0]][pos[1]] == 0:\n",
    "                    is_island = False\n",
    "                    break\n",
    "            \n",
    "            if is_island:\n",
    "                count += 1\n",
    "                \n",
    "        return count\n",
    "    \n",
    "    def isvalid(self, grid, x, y):\n",
    "        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) and grid[x][y] == 1\n",
    "                    \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        \n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "        \"\"\"\n",
    "        def dfs(grid, i, j, idx, searched):\n",
    "            if searched[i][j] == 1:\n",
    "                return\n",
    "            searched[i][j] = 1\n",
    "            grid[i][j] = idx\n",
    "            if i > 0:\n",
    "                dfs(grid, i-1, j, idx, searched)\n",
    "            if i < m-1:\n",
    "                dfs(grid, i+1, j, idx, searched)\n",
    "            if j > 0:\n",
    "                dfs(grid, i, j-1, idx, searched)\n",
    "            if j < n-1:\n",
    "                dfs(grid, i, j+1, idx, searched)\n",
    "        \n",
    "        searched = [[0 for j in range(n)] for i in range(m)]\n",
    "        count_idx = 0\n",
    "        for i in range(m)\n",
    "            for j in range(n):\n",
    "                count_idx = 0\n",
    "                dfs(grid2, i, j, 0)\n",
    "        \"\"\"\n",
    "        class UnionFindSet(object):\n",
    "            def __init__(self, data_list):\n",
    "                self.father_dict = {}\n",
    "                self.size_dict = {}\n",
    "\n",
    "                for node in data_list:\n",
    "                    self.father_dict[node] = node\n",
    "                    self.size_dict[node] = 1\n",
    "\n",
    "            def find_head(self, node):\n",
    "                father = self.father_dict[node]\n",
    "                if(node != father):\n",
    "                    father = self.find_head(father)\n",
    "                self.father_dict[node] = father\n",
    "                return father\n",
    "\n",
    "            def is_same_set(self, node_a, node_b):\n",
    "                return self.find_head(node_a) == self.find_head(node_b)\n",
    "\n",
    "            def union(self, node_a, node_b):\n",
    "                if node_a is None or node_b is None:\n",
    "                    return\n",
    "\n",
    "                a_head = self.find_head(node_a)\n",
    "                b_head = self.find_head(node_b)\n",
    "\n",
    "                if(a_head != b_head):\n",
    "                    a_set_size = self.size_dict[a_head]\n",
    "                    b_set_size = self.size_dict[b_head]\n",
    "                    if(a_set_size >= b_set_size):\n",
    "                        self.father_dict[b_head] = a_head\n",
    "                        self.size_dict[a_head] = a_set_size + b_set_size\n",
    "                    else:\n",
    "                        self.father_dict[a_head] = b_head\n",
    "                        self.size_dict[b_head] = a_set_size + b_set_size\n",
    "        data = [i for i in range(m*n)]\n",
    "        union = UnionFindSet(data)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid2[i][j] == 1 and grid2[i-1][j] == 1:\n",
    "                    union.union(i+j*m, i-1+j*m)\n",
    "                if j > 0 and grid2[i][j] == 1 and grid2[i][j-1] == 1:\n",
    "                    union.union(i+j*m, i+(j-1)*m)\n",
    "        \n",
    "        wait_to_judge = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    #print(i, j, i+j*m, \"SecIsland\")\n",
    "                    wait_to_judge.setdefault(union.find_head(i+j*m), 0)\n",
    "                    wait_to_judge[union.find_head(i+j*m)] += 1\n",
    "                    if grid1[i][j] != 1:\n",
    "                        wait_to_judge[union.find_head(i+j*m)] = -10e7\n",
    "        ans = 0\n",
    "        for k, v in wait_to_judge.items():\n",
    "            #print(k, v)\n",
    "            if v > 0:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.size = [1] * n\n",
    "        self.fa = list(range(n))\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.size[fx] < self.size[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.fa[fy] = fx\n",
    "        self.size[fx] += self.size[fy]\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "\n",
    "        uf2 = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if j < n - 1 and grid2[i][j] == 1 and grid2[i][j + 1] == 1:\n",
    "                    uf2.union(index, index + 1)\n",
    "                if i < m - 1 and grid2[i][j] == 1 and grid2[i + 1][j] == 1:\n",
    "                    index_j = (i + 1) * n + j\n",
    "                    uf2.union(index, index_j)\n",
    "\n",
    "        graph2 = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    index = i * n + j\n",
    "                    graph2[uf2.find(index)].append([i, j])\n",
    "\n",
    "        ans = len(graph2)\n",
    "        for k, v in graph2.items():\n",
    "            for i, j in v:\n",
    "                if grid1[i][j] == 0:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Disjoint:\n",
    "    \"\"\"这是一个并查集的类\"\"\"\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.rank = [1]*n\n",
    "        self.f = list(range(n))\n",
    "    def find(self, x):\n",
    "        \"\"\"找集合的根，路径压缩\"\"\"\n",
    "        if self.f[x] == x:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def union(self, x, y):\n",
    "        \"\"\"大集合并入小集合\"\"\"\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return # 本来就是连通集\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            self.rank[fy] += self.rank[fx]\n",
    "            self.f[fx] = fy\n",
    "        else:\n",
    "            self.rank[fx] += self.rank[fy]\n",
    "            self.f[fy] = fx\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        \"\"\"返回 grid2 中子岛屿的数目\"\"\"\n",
    "        row, col = len(grid2), len(grid2[0])\n",
    "        disjoint = Disjoint(row*col)\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid2[i][j] == 1:\n",
    "                    for a, b in [(i,j+1),(i+1,j)]: # 遍历一个陆地的右和下，防止重复遍历\n",
    "                        if 0 <= a <= row-1 and 0 <= b <= col-1: # 不越界的情况下\n",
    "                            if grid2[a][b] == 1:\n",
    "                                disjoint.union(i*col+j,a*col+b) # 两个坐标进行合并\n",
    "        # 将不同的连通分量包含的坐标均列出来\n",
    "        island = defaultdict(list)\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid2[i][j] == 1:\n",
    "                    x = disjoint.find(i*col+j)\n",
    "                    island[x].append((i,j)) # 将坐标元组加入列表中\n",
    "        cnt = 0 # 统计子岛屿的数量\n",
    "        for key,value in island.items():\n",
    "            flag = 1\n",
    "            for x,y in value:\n",
    "                if grid1[x][y] == 0:\n",
    "                    flag = 0 # 该岛屿不是子岛屿\n",
    "            if flag:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        g1set, g2set = {}, {}\n",
    "        row, col = len(grid1), len(grid1[0])\n",
    "        dy2set = defaultdict(set)\n",
    "        one2twomap = {}\n",
    "        def findset(g, idx):\n",
    "            if idx not in g:\n",
    "                g[idx] = idx\n",
    "            elif g[idx] != idx:\n",
    "                g[idx] = findset(g, g[idx])\n",
    "            return g[idx]\n",
    "        def union(g, idx1, idx2):\n",
    "            f1, f2 = findset(g, idx1), findset(g, idx2)\n",
    "            if f1 != f2:\n",
    "                g[f2] = f1\n",
    "        for m, gtemp in enumerate(grid1):\n",
    "            for n, g1 in enumerate(gtemp):\n",
    "                g2 = grid2[m][n]\n",
    "                if g1 == 1 and m > 0 and grid1[m - 1][n] == 1:\n",
    "                    union(g1set, m * col + n, m * col + n - col)\n",
    "                if g1 == 1 and n > 0 and grid1[m][n - 1] == 1:\n",
    "                    union(g1set, m * col + n, m * col + n - 1)\n",
    "                if g2 == 1 and m > 0 and grid2[m - 1][n] == 1:\n",
    "                    union(g2set, m * col + n, m * col + n - col)\n",
    "                if g2 == 1 and n > 0 and grid2[m][n - 1] == 1:\n",
    "                    union(g2set, m * col + n, m * col + n - 1)\n",
    "        for m, gtemp in enumerate(grid2):\n",
    "            for n, g2 in enumerate(gtemp):\n",
    "                if g2 == 1:\n",
    "                    s2 = findset(g2set, m * col + n)\n",
    "                    dy2set[s2].add((m, n))\n",
    "        ans = 0\n",
    "        for s2 in dy2set:\n",
    "            flag = True\n",
    "            for m, n in dy2set[s2]:\n",
    "                if grid1[m][n] != 1:\n",
    "                    flag = False\n",
    "                    break\n",
    "                s1 = findset(g1set, m * col + n)\n",
    "                if s2 not in one2twomap:\n",
    "                    one2twomap[s2] = s1\n",
    "                elif one2twomap[s2] != s1:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans += 1\n",
    "        return ans\n",
    "                \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j]==0 and grid2[i][j]==1:\n",
    "                    self.dfs(grid2, i, j)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==1:\n",
    "                    res += 1\n",
    "                    self.dfs(grid2, i, j)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if i<0 or j<0 or i>=m or j>=n:\n",
    "            return\n",
    "        if grid[i][j]==0:\n",
    "            return\n",
    "        grid[i][j] = 0\n",
    "        self.dfs(grid, i+1, j)\n",
    "        self.dfs(grid, i-1, j)\n",
    "        self.dfs(grid, i, j-1)\n",
    "        self.dfs(grid, i, j+1)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        from collections import deque\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        parents = {}\n",
    "        ranks = {}\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 1:\n",
    "                    parents[i * n + j] = i * n + j\n",
    "                    ranks[i * n + j] = 0\n",
    "        def find(i):\n",
    "            if i != parents[i]:\n",
    "                parents[i] = find(parents[i])\n",
    "            return parents[i]\n",
    "        def union(i, j):\n",
    "            x, y = find(i), find(j)\n",
    "            if x != y:\n",
    "                if ranks[x] <= ranks[y]:\n",
    "                    parents[x] = y\n",
    "                    if ranks[x] == ranks[y]:\n",
    "                        ranks[y] += 1\n",
    "                else:\n",
    "                    parents[y] = x\n",
    "        def isConnected(i, j):\n",
    "            return find(i) == find(j)\n",
    "        def bfs(i, j):\n",
    "            nonlocal m, n\n",
    "            prev = None\n",
    "            queue = deque()\n",
    "            queue.append([i, j])\n",
    "            grid1[i][j] = 0\n",
    "            while queue:\n",
    "                x, y = queue.popleft()\n",
    "                if prev is not None:\n",
    "                    union(prev, x * n + y)\n",
    "                prev = x * n + y\n",
    "                for oi, oj in dirs:\n",
    "                    ni, nj = oi + x, oj + y\n",
    "                    if 0 <= ni < m and 0 <= nj < n and grid1[ni][nj] == 1:\n",
    "                        queue.append([ni, nj])\n",
    "                        grid1[ni][nj] = 0\n",
    "        def dfs(i, j):\n",
    "            nonlocal m, n\n",
    "            result = True\n",
    "            stack = []\n",
    "            stack.append([i, j])\n",
    "            grid2[i][j] = 0\n",
    "            prev = None\n",
    "            while stack:\n",
    "                x, y = stack.pop()\n",
    "                if x * n + y not in parents:\n",
    "                    result = False\n",
    "                if prev is not None and x * n + y in parents and not isConnected(prev, x * n + y):\n",
    "                    result = False\n",
    "                if  x * n + y in parents:\n",
    "                    prev = x * n + y\n",
    "                for oi, oj in dirs:\n",
    "                    ni, nj = oi + x, oj + y\n",
    "                    if 0 <= ni < m and 0 <= nj < n and grid2[ni][nj] == 1:\n",
    "                        grid2[ni][nj] = 0\n",
    "                        stack.append([ni, nj])\n",
    "            return result\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 1:\n",
    "                    bfs(i, j)\n",
    "        # print(parents)\n",
    "        # print(grid1)\n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    if dfs(i, j):\n",
    "                        result += 1\n",
    "        # print(grid2)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "\n",
    "        #标准的ufs做法\n",
    "\n",
    "        def ufs(n):\n",
    "            return list(range(n)),[0]*n\n",
    "\n",
    "        def find(p,x):\n",
    "            while p[x]!=x:\n",
    "                p[x]=p[p[x]]\n",
    "                x=p[x]\n",
    "            return x\n",
    "\n",
    "        def union(p,r,x,y):\n",
    "            px=find(p,x)\n",
    "            py=find(p,y)\n",
    "            if px==py:\n",
    "                return \n",
    "            if r[px]>r[py]:\n",
    "                p[py]=px\n",
    "            elif r[px]<r[py]:\n",
    "                p[px]=py\n",
    "            else:\n",
    "                p[px]=py\n",
    "                r[py]+=1\n",
    "\n",
    "        m,n=len(grid1),len(grid1[0])\n",
    "\n",
    "        p1,r1=ufs(m*n)\n",
    "        p2,r2=ufs(m*n)\n",
    "\n",
    "        def merge(grid,p,r):\n",
    "            m,n=len(grid),len(grid[0])\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==1:\n",
    "                        for (i2,j2) in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):\n",
    "                            if 0<=i2<m and 0<=j2<n and grid[i2][j2]==1:\n",
    "                                union(p,r,i*n+j,i2*n+j2)\n",
    "        \n",
    "        merge(grid1,p1,r1)\n",
    "        merge(grid2,p2,r2)\n",
    "\n",
    "        lands=collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==1:\n",
    "                    lands[find(p2,i*n+j)].append((i,j))\n",
    "        ans=0\n",
    "        for k,lis in lands.items():\n",
    "            i,j=divmod(k,n)\n",
    "            if grid1[i][j]==0:\n",
    "                continue\n",
    "            pk=find(p1,k)\n",
    "            if all(find(p1,i*n+j)==pk for i,j in lis):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self):\n",
    "        self.hash_dict = {}\n",
    "    \n",
    "    def find(self, u):\n",
    "        if u not in self.hash_dict.keys():\n",
    "            self.hash_dict[u] = u\n",
    "            return u\n",
    "        elif self.hash_dict[u] == u:\n",
    "            return u\n",
    "        else:\n",
    "            self.hash_dict[u] = self.find(self.hash_dict[u])\n",
    "            return self.hash_dict[u]\n",
    "        \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v:\n",
    "            ''\n",
    "        else:\n",
    "            self.hash_dict[u] = v\n",
    "\n",
    "    def is_same(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return v == u\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1, grid2) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        # step 1 构建连通图\n",
    "        tool_1 = UnionSet()\n",
    "        tool_2 = UnionSet()\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                # if grid1[i][j] == 1 and i + 1 < m and grid1[i+1][j] == 1:\n",
    "                #     tool_1.join((i, j), (i+1, j))\n",
    "                # if grid1[i][j] == 1 and j + 1 < n and grid1[i][j+1] == 1:\n",
    "                #     tool_1.join((i, j), (i, j+1))\n",
    "                if grid2[i][j] == 1 and i + 1 < m and grid2[i+1][j] == 1:\n",
    "                    tool_2.join((i, j), (i+1, j))\n",
    "                if grid2[i][j] == 1 and j + 1 < n and grid2[i][j+1] == 1:\n",
    "                    tool_2.join((i, j), (i, j+1))\n",
    "        \n",
    "        # step 2 整理\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                # if grid1[i][j] == 1:\n",
    "                #     tool_1.find((i, j))\n",
    "                if grid2[i][j] == 1:\n",
    "                    tool_2.find((i, j))\n",
    "\n",
    "        # step 3 构建分组\n",
    "        # cluster_dict_1 = {}\n",
    "        cluster_dict_2 = {}\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                # if grid1[i][j] == 1: \n",
    "                #     if tool_1.hash_dict[(i, j)] not in cluster_dict_1.keys():\n",
    "                #         cluster_dict_1[tool_1.hash_dict[(i, j)]] = set()\n",
    "                #     cluster_dict_1[tool_1.hash_dict[(i, j)]].add((i, j))\n",
    "                if grid2[i][j] == 1: \n",
    "                    if tool_2.hash_dict[(i, j)] not in cluster_dict_2.keys():\n",
    "                        cluster_dict_2[tool_2.hash_dict[(i, j)]] = set()\n",
    "                    cluster_dict_2[tool_2.hash_dict[(i, j)]].add((i, j))\n",
    "        \n",
    "        # step 4 利用集合交集 a & b = b 来确定子岛屿数量\n",
    "        count = 0\n",
    "        for key in cluster_dict_2.keys():\n",
    "            flag = True\n",
    "            for point in cluster_dict_2[key]:\n",
    "                i, j = point\n",
    "                if grid1[i][j] != 1:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        # s1. traverse grid2, if land in grid2 but is water in grid1, floodfill it by using dfs\n",
    "        # s2. traverse grid2 again, how many island in grid2\n",
    "        # s3. dfs function -> floodfill island with water\n",
    "\n",
    "        def dfs(grid, row, col):\n",
    "            if row<0 or row>=len(grid) or col<0 or col>=len(grid[0]) or grid[row][col]==0:\n",
    "                return \n",
    "            grid[row][col] = 0\n",
    "            dfs(grid, row+1, col)\n",
    "            dfs(grid, row-1, col)\n",
    "            dfs(grid, row, col+1)\n",
    "            dfs(grid, row, col-1)\n",
    "\n",
    "        for row in range(len(grid2)):\n",
    "            for col in range(len(grid2[0])):\n",
    "                if grid2[row][col] == 1 and grid1[row][col] == 0:\n",
    "                    dfs(grid2, row, col)\n",
    "        \n",
    "        count = 0\n",
    "        for row in range(len(grid2)):\n",
    "            for col in range(len(grid2[0])):\n",
    "                if grid2[row][col] == 1:\n",
    "                    count += 1\n",
    "                    dfs(grid2, row, col)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                # 如果说在岛屿1中是海水，在岛屿2中是陆地，那肯定不是子岛屿\n",
    "                if grid1[row][col] == 0 and grid2[row][col] == 1:\n",
    "                    self.dfs(grid2, row, col)\n",
    "\n",
    "        # 现在岛屿2中剩下的岛屿都是子岛屿了，统计岛屿数量\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if grid2[row][col] == 1:\n",
    "                    res += 1\n",
    "                    self.dfs(grid2, row, col)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def dfs(self, grid, row, col):\n",
    "        # base case:防止 i 和 j 越界，也就是防止超出岛屿（上下左右）的范围。特别注意当遍历到海洋的时候也退出循环\n",
    "        if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] == 0:\n",
    "            return\n",
    "\n",
    "        # 将遍历过的陆地改为海洋，防止重复遍历\n",
    "        grid[row][col] = 0\n",
    "        # 访问相邻节点\n",
    "        self.dfs(grid, row - 1, col)\n",
    "        self.dfs(grid, row + 1, col)\n",
    "        self.dfs(grid, row, col - 1)\n",
    "        self.dfs(grid, row, col + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "\n",
    "        def dfs(grid, i, j):\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:\n",
    "                grid[i][j] = 0\n",
    "                dfs(grid, i+1, j)\n",
    "                dfs(grid, i-1, j)\n",
    "                dfs(grid, i, j+1)\n",
    "                dfs(grid, i, j-1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    dfs(grid2, i, j)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    dfs(grid2, i, j)\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        rows, cols = len(grid1), len(grid1[0])\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    self.dfs(grid2, i, j)\n",
    "        \n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    self.dfs(grid2, i, j)\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def dfs(self, grid, i, j):\n",
    "\n",
    "        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "            return \n",
    "        \n",
    "\n",
    "        if grid[i][j] == 0:\n",
    "            return \n",
    "        \n",
    "        grid[i][j] = 0\n",
    "\n",
    "        self.dfs(grid, i + 1, j)\n",
    "        self.dfs(grid, i - 1, j)\n",
    "        self.dfs(grid, i, j + 1)\n",
    "        self.dfs(grid, i, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        # 由题可知：B 岛的岛屿所有土地需要在 A 岛对应位置也是陆地才算子岛屿\n",
    "        # 其他一样 使用DFS-FloodFill\n",
    "\n",
    "        # 重点：先将非子岛的淹掉，再去计算数量\n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j]==0 and grid2[i][j]==1:\n",
    "                    self.dfs(grid2,i,j)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j]==1 and grid2[i][j]==1:\n",
    "                    res+=1\n",
    "                self.dfs(grid2,i,j)\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def dfs(self,grid: List[List[int]],i:int,j:int):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if i < 0 or j < 0 or i >= m or j >= n:\n",
    "            # 边界管理\n",
    "            return\n",
    "        if grid[i][j] == 0:\n",
    "            # 已经是海洋了\n",
    "            return\n",
    "        # 淹没陆地，成为海洋\n",
    "        grid[i][j]=0\n",
    "        self.dfs(grid, i + 1, j)\n",
    "        self.dfs(grid, i, j + 1)\n",
    "        self.dfs(grid, i - 1, j)\n",
    "        self.dfs(grid, i, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    # 不是子岛，淹没掉\n",
    "                    self.dfs(grid2, i, j)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    self.dfs(grid2, i, j)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if i < 0 or j < 0 or i >= m or j >= n:\n",
    "            return\n",
    "\n",
    "        if grid[i][j] == 0:\n",
    "            return\n",
    "\n",
    "        grid[i][j] = 0\n",
    "\n",
    "        self.dfs(grid, i - 1, j)\n",
    "        self.dfs(grid, i + 1, j)\n",
    "        self.dfs(grid, i, j - 1)\n",
    "        self.dfs(grid, i, j + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        res = 0\n",
    "        def dfs(i, j):\n",
    "            if not 0 <= i < m or not 0 <= j < n or grid2[i][j] == 0:return\n",
    "            grid2[i][j] = 0\n",
    "            dfs(i + 1, j)\n",
    "            dfs(i - 1, j)\n",
    "            dfs(i, j + 1)\n",
    "            dfs(i, j - 1)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and grid1[i][j] == 0:\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    dfs(i, j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        dd=[[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        def dfs(grid,i,j):\n",
    "            grid[i][j]=0\n",
    "            for dx,dy in dd:\n",
    "                x,y=i+dx,j+dy\n",
    "                if len(grid)>x>=0 and 0<=y<len(grid[0]) and grid[x][y]==1:\n",
    "                    dfs(grid,x,y)\n",
    "\n",
    "        for i in range(len(grid2)):\n",
    "            for j in range(len(grid2[0])):\n",
    "                if grid1[i][j]==0 and grid2[i][j]==1:\n",
    "                    dfs(grid2,i,j)\n",
    "        count=0\n",
    "        for i in range(len(grid2)):\n",
    "            for j in range(len(grid2[0])):\n",
    "                if grid2[i][j]==1:\n",
    "                    dfs(grid2,i,j)\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m, n =len(grid1), len(grid1[0])\n",
    "        dirs = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "\n",
    "        def dfs(i, j, grid):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return\n",
    "            \n",
    "            if grid[i][j] == 0:\n",
    "                return\n",
    "            \n",
    "            grid[i][j] = 0\n",
    "            for d in dirs:\n",
    "                dfs(i+d[0],j+d[1],grid)\n",
    "        \n",
    "        # 从不可能是子岛屿的地块开始dfs\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    dfs(i, j, grid2)\n",
    "        \n",
    "        # 剩余的地块都是子岛屿的一部分，统计子岛屿数量\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    dfs(i, j, grid2)\n",
    "                    res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    self.dfs(grid2, i, j)\n",
    "                    \n",
    "        res = 0 \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid2[r][c]==1:\n",
    "                    res+=1\n",
    "                    self.dfs(grid2, r,c)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, grid, r, c):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if not 0 <= r < m or not 0 <= c < n or grid[r][c] == 0:\n",
    "            return\n",
    "        grid[r][c] = 0\n",
    "        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "            nr = r + dx\n",
    "            nc = c + dy\n",
    "            self.dfs(grid, nr, nc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or grid2[i][j] != 1:\n",
    "                return\n",
    "            grid2[i][j] = 0\n",
    "            dirs = ((1, 0), (-1, 0), (0, 1), (0, -1),)\n",
    "            for dx, dy in dirs:\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                dfs(x, y)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and grid1[i][j] == 0:\n",
    "                    dfs(i,j)\n",
    "        \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    dfs(i,j)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "\n",
    "        def dfs(grid, i, j):\n",
    "            grid[i][j] = 0\n",
    "            dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "            for di, dj in dirs:\n",
    "                newi, newj = i+di, j+dj\n",
    "                if 0<=newi<m and 0<=newj<n and grid[newi][newj] == 1:\n",
    "                    dfs(grid, newi, newj)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and grid1[i][j] == 0:\n",
    "                    dfs(grid2, i, j)\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    dfs(grid2, i, j)\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    self.backtrack(grid2, i, j)\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    self.backtrack(grid2, i, j)\n",
    "        \n",
    "        return res\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "    def backtrack(self, grid2, i, j):\n",
    "        if i < 0 or j < 0 or i >= len(grid2) or j >= len(grid2[0]) or grid2[i][j] == 0:\n",
    "            return\n",
    "        \n",
    "        grid2[i][j] = 0\n",
    "        direction = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "        for x, y in direction:\n",
    "            self.backtrack(grid2, x + i, y + j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m,n = len(grid1), len(grid2[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j]==0 and grid2[i][j]==1:\n",
    "                    self.dfs(grid2, i, j)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==1:\n",
    "                    ans+=1\n",
    "                    self.dfs(grid2,i,j)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if not 0<=i<m or not 0<=j<n:\n",
    "            return\n",
    "        if grid[i][j]==0:\n",
    "            return\n",
    "        grid[i][j] = 0\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for x, y in dirs:\n",
    "            nr = i + x\n",
    "            nc = j + y\n",
    "            self.dfs(grid, nr, nc)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\r\n",
    "        def in_area(i, j):\r\n",
    "            return 0 <= i < len(grid2) and 0 <= j < len(grid2[0])\r\n",
    "\r\n",
    "        def dfs(i, j):\r\n",
    "            if not in_area(i, j) or grid2[i][j] == 0:\r\n",
    "                return 1\r\n",
    "            if grid1[i][j] == 0:\r\n",
    "                return 0\r\n",
    "            grid2[i][j] = 0\r\n",
    "            return dfs(i, j-1) & dfs(i, j+1) & dfs(i-1, j) & dfs(i+1, j)\r\n",
    "            \r\n",
    "        ans = 0\r\n",
    "        for i in range(len(grid2)):\r\n",
    "            for j in range(len(grid2[0])):\r\n",
    "                if grid2[i][j] == 1:\r\n",
    "                    if dfs(i, j):\r\n",
    "                        ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid2[0])\n",
    "        def dfs(x, y):\n",
    "            if x<0 or x>=m or y<0 or y>=n:\n",
    "                return\n",
    "            if grid2[x][y] == 0:\n",
    "                return\n",
    "            grid2[x][y] = 0\n",
    "            dfs(x-1, y)\n",
    "            dfs(x, y-1)\n",
    "            dfs(x+1, y)\n",
    "            dfs(x, y+1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and grid1[i][j] == 0:\n",
    "                    dfs(i, j)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res = res + 1\n",
    "                    dfs(i, j)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "\n",
    "        def dfs(grid, i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return \n",
    "\n",
    "            if grid[i][j] == 0:\n",
    "                return \n",
    "\n",
    "            grid[i][j] = 0\n",
    "\n",
    "            dfs(grid, i, j-1)\n",
    "            dfs(grid, i, j+1)\n",
    "            dfs(grid, i-1, j)\n",
    "            dfs(grid, i+1, j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and grid1[i][j] == 0:\n",
    "                    dfs(grid2,i,j)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    dfs(grid2, i, j)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        if len(grid1) == 0 or len(grid2[0]) == 0:\n",
    "            return 0\n",
    "        if len(grid2) == 0 or len(grid2[0]) == 0:\n",
    "            return 0\n",
    "        if len(grid1) != len(grid2) or len(grid1[0]) != len(grid2[0]):\n",
    "            return 0\n",
    "        res = 0\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        def dfs(grid, i, j):\n",
    "            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):\n",
    "                return True\n",
    "            if grid[i][j] != 2:\n",
    "                return grid[i][j] == 0\n",
    "            grid[i][j] = 0\n",
    "            down = dfs(grid, i-1, j)\n",
    "            up = dfs(grid, i+1, j)\n",
    "            left = dfs(grid, i, j-1)\n",
    "            right = dfs(grid, i, j+1)\n",
    "            return down and up and left and right\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    grid2[i][j] += grid1[i][j]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 2 and dfs(grid2, i, j):\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "\n",
    "        row = len(grid1)\n",
    "        col = len(grid1[0])\n",
    "\n",
    "        # flood 1 with 0\n",
    "        def dfs_flood(i,j):\n",
    "            if i < 0 or i >= row or j < 0 or j >= col:\n",
    "                return\n",
    "            \n",
    "            if grid2[i][j] == 0:\n",
    "                return\n",
    "            \n",
    "            grid2[i][j] = 0\n",
    "\n",
    "            # up\n",
    "            dfs_flood(i-1,j)\n",
    "            # right\n",
    "            dfs_flood(i,j+1)\n",
    "            # down\n",
    "            dfs_flood(i+1,j)\n",
    "            # left\n",
    "            dfs_flood(i,j-1)\n",
    "        \n",
    "        # if grid1 is 0 and grid2 is 1, we flood the islands\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    dfs_flood(i,j)\n",
    "\n",
    "        # find the number of remaining islands in grid2\n",
    "        result = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid2[i][j] == 1:\n",
    "                    result += 1\n",
    "                    dfs_flood(i,j)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "        def foo(i, j):\n",
    "            grid2[i][j] = 0\n",
    "            flag = grid1[i][j] == 1\n",
    "            if i > 0 and grid2[i - 1][j] == 1:\n",
    "                flag &= foo(i - 1, j)\n",
    "            if j > 0 and grid2[i][j - 1] == 1:\n",
    "                flag &= foo(i, j - 1)\n",
    "            if i < len(grid2) - 1 and grid2[i + 1][j] == 1:\n",
    "                flag &= foo(i + 1, j)\n",
    "            if j < len(grid2[0]) - 1 and grid2[i][j + 1] == 1:\n",
    "                flag &= foo(i, j + 1)\n",
    "            return flag\n",
    "\n",
    "        return sum(grid2[i][j] and foo(i, j) for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        \n",
    "        self.flag = True\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or i > m-1 or j < 0 or j > n-1:\n",
    "                return \n",
    "            if grid2[i][j] == 0:\n",
    "                return \n",
    "            if grid2[i][j] == 1:\n",
    "                grid2[i][j] = 0\n",
    "                if grid1[i][j] == 0:\n",
    "                    self.flag = False\n",
    "                dfs(i+1, j)\n",
    "                dfs(i, j-1)\n",
    "                dfs(i, j+1)\n",
    "                dfs(i-1, j)\n",
    "        res = 0\n",
    "        m, n = len(grid2), len(grid2[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    self.flag = True\n",
    "                    dfs(i, j)\n",
    "                    if self.flag:\n",
    "                        res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        total_count = 0\n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            nonlocal grid2, valid\n",
    "            if i < 0 or i >= m:\n",
    "                return True\n",
    "            if j < 0 or j >= n:\n",
    "                return True\n",
    "            if grid2[i][j] == 0:\n",
    "                return True\n",
    "            elif grid2[i][j] == 1:\n",
    "                grid2[i][j] = 0\n",
    "                if grid1[i][j] == 0:\n",
    "                    valid = False\n",
    "                dfs(i+1, j)\n",
    "                dfs(i-1, j)\n",
    "                dfs(i, j+1)\n",
    "                dfs(i, j-1)\n",
    "                # if i == 2 and j == 1:\n",
    "                #     print(\"debug\", valid, valid_surr)\n",
    "                return True\n",
    "                # return valid_surr and valid\n",
    "\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    valid = True\n",
    "                    dfs(i, j)\n",
    "                    # print(i, j, valid)\n",
    "                    if valid:\n",
    "                        total_count +=1\n",
    "        return total_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        self.grid1 = grid1\n",
    "        self.grid2 = grid2\n",
    "        self.length = len(self.grid1)\n",
    "        self.width = len(self.grid1[0])\n",
    "        self.directions = [\n",
    "            (0, 1), \n",
    "            (0, -1), \n",
    "            (1, 0), \n",
    "            (-1, 0)\n",
    "        ]\n",
    "        num_subisland = 0\n",
    "        for i in range(self.length):\n",
    "            for j in range(self.width):\n",
    "                if self.grid2[i][j] == 1:\n",
    "                    num_subisland += self.dfs(i, j)\n",
    "        return num_subisland\n",
    "\n",
    "\n",
    "    \n",
    "    def dfs(self, x, y):\n",
    "        self.grid2[x][y] = 0\n",
    "        is_subisland = 1\n",
    "        if self.grid1[x][y] == 0:\n",
    "            is_subisland = 0\n",
    "        for dx, dy in self.directions:\n",
    "            nextx = x + dx\n",
    "            nexty = y + dy\n",
    "            if nextx >= 0 and nextx < self.length and nexty >= 0 and nexty < self.width and self.grid2[nextx][nexty] == 1:\n",
    "                retval = self.dfs(nextx, nexty)\n",
    "                if retval == 0:\n",
    "                    is_subisland = 0\n",
    "        return is_subisland"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\r\n",
    "        grid = grid2\r\n",
    "        n, m = len(grid), len(grid[0])\r\n",
    "        self.vis = [[0 for _ in range(m)] for _ in range(n)]\r\n",
    "        res = 0\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(m):\r\n",
    "                if grid[i][j] == 1 and not self.vis[i][j]:\r\n",
    "                    self.flag = True\r\n",
    "                    self.dfs(grid1, grid, i, j)\r\n",
    "                    if self.flag:\r\n",
    "                         res += 1\r\n",
    "        return res\r\n",
    "    \r\n",
    "    def dfs(self, grid1, grid, i, j):\r\n",
    "        if grid1[i][j] == 0:\r\n",
    "             self.flag = False\r\n",
    "        self.vis[i][j] = 1\r\n",
    "        n, m = len(grid), len(grid[0])\r\n",
    "        for d in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\r\n",
    "            ii, jj = i + d[0], j + d[1]\r\n",
    "            if 0 <= ii <= n-1 and 0 <= jj <= m-1 and grid[ii][jj] == 1 and not self.vis[ii][jj]:\r\n",
    "                    self.dfs(grid1, grid, ii, jj)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=len(grid2) or y>=len(grid2[0]) or grid2[x][y]==0:\n",
    "                return True\n",
    "            if grid1[x][y]==0:\n",
    "                return False\n",
    "            grid2[x][y]=0\n",
    "            res=True\n",
    "            for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                res=res & dfs(x+i,y+j)\n",
    "            return res\n",
    "\n",
    "        \n",
    "        cont=0\n",
    "        for i in range(len(grid2)):\n",
    "            for j in range(len(grid2[0])):\n",
    "                if grid2[i][j]==1 and dfs(i,j):\n",
    "                    cont+=1\n",
    "        return cont"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        res = 0\n",
    "        def dfs(x, y):\n",
    "            # 代表已经遍历过\n",
    "            nonlocal ok\n",
    "            grid2[x][y] = 0\n",
    "            if grid1[x][y] == 0: # 2中为陆地的部分在1中是水\n",
    "                ok = False\n",
    "            for dx, dy in dirs:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if 0<=nx<m and 0<=ny<n and grid2[nx][ny] > 0:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    ok = True\n",
    "                    dfs(i, j)\n",
    "                    if ok:\n",
    "                        res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dr = [[0,1], [1, 0], [-1, 0], [0, -1]]\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        n, m = len(grid1), len(grid1[0])\n",
    "        def dfs(x, y):\n",
    "            nonlocal flag, m, n\n",
    "            if grid1[x][y] != 1:\n",
    "                flag = False\n",
    "            grid2[x][y] = 2\n",
    "            for d in dr:\n",
    "                nx, ny = x + d[0], y + d[1]\n",
    "                if 0<=nx<n and 0<=ny<m and grid2[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] == 1:\n",
    "                    flag = True\n",
    "                    dfs(i, j)\n",
    "                    # print(i, j, flag)\n",
    "                    if flag:\n",
    "                        res += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        n, m = len(grid1), len(grid1[0])\n",
    "        Same = True\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x >= n or y < 0 or y >= m or grid2[x][y] != 1: return \n",
    "\n",
    "            # grid2[x][y] = 0\n",
    "            nonlocal Same\n",
    "            if grid1[x][y] != 1: \n",
    "                Same = False\n",
    "\n",
    "            grid2[x][y] = 2\n",
    "            for dx, dy in directions:\n",
    "                dfs(x + dx, y + dy)\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j] == 1:\n",
    "\n",
    "                    dfs(i, j)\n",
    "\n",
    "                    if Same:\n",
    "                        res += 1\n",
    "                    Same = True\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        # 只淹没grid1，grid2不动\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        directions = [\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "            [-1, 0],\n",
    "            [1, 0],\n",
    "        ]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if not (0<=x<m and 0<=y<n):\n",
    "                return True\n",
    "            if grid2[x][y] == 0:\n",
    "                return True\n",
    "\n",
    "            flag = True\n",
    "            if grid2[x][y] == 1 and grid1[x][y] == 0:\n",
    "                flag = False\n",
    "            grid2[x][y] = 0\n",
    "            for d in directions:\n",
    "                x_nx = x + d[0]\n",
    "                y_nx = y + d[1]\n",
    "                flag = flag & dfs(x_nx, y_nx)\n",
    "            return flag\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    temp = dfs(i, j)\n",
    "                    if temp: res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        def dfs(grid2, i, j):\n",
    "            nonlocal flag\n",
    "            if not 0 <= i < len(grid2) or not 0 <= j < len(grid2[0]) or grid2[i][j] in [0, 2]: return\n",
    "            \n",
    "            grid2[i][j] = 2\n",
    "            flag = flag and grid1[i][j] == 1\n",
    "\n",
    "            dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "            for d in dirs:\n",
    "                dfs(grid2, i + d[0], j + d[1])\n",
    "        \n",
    "        res = 0\n",
    "        row, col = len(grid2), len(grid2[0])\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid2[i][j] == 1:\n",
    "                    flag = True\n",
    "                    dfs(grid2, i, j)\n",
    "                    res = res + 1 if flag else res \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        #dfs解法\n",
    "        m,n=len(grid2),len(grid2[0])\n",
    "        dirctions=[(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        def dfs(x,y):\n",
    "            vis.add((x,y))\n",
    "            grid2[x][y]=0\n",
    "            for i,j in dirctions:\n",
    "                new_x,new_y=x+i,y+j\n",
    "                if 0<=new_x<m and 0<=new_y<n and grid2[new_x][new_y]==1:\n",
    "                    dfs(new_x,new_y)\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==1:\n",
    "                    vis=set()\n",
    "                    dfs(i,j)\n",
    "                    for x,y in vis:\n",
    "                        if grid1[x][y]==0: break\n",
    "                    else: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i<0 or i>=m or j<0 or j>=n or grid2[i][j] == 0:\n",
    "                return True\n",
    "            if grid1[i][j] == 0:\n",
    "                return False\n",
    "            grid2[i][j] = 0\n",
    "            res = True\n",
    "            directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "            for dx, dy in directions:\n",
    "                res = dfs(i+dx, j+dy) and res\n",
    "            return res\n",
    "\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and dfs(i,j):\n",
    "                    count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "        ans = 0\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        \n",
    "        def dfs(i,j):\n",
    "            nonlocal oneisland\n",
    "            if i <0 or i >=m or j < 0 or j >=n:\n",
    "                return\n",
    "            if grid2[i][j] == 0:\n",
    "                return\n",
    "            if visited[i][j] == 1:\n",
    "                return\n",
    "            if grid1[i][j] == 0:\n",
    "                oneisland = False\n",
    "\n",
    "\n",
    "            visited[i][j] = 1\n",
    "            for d in directions:\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]    \n",
    "                dfs(x,y)\n",
    "                    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1 and visited[i][j] == 0:  \n",
    "                    oneisland = True       \n",
    "                    dfs(i,j)\n",
    "                    if oneisland:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] ==1:\n",
    "                    if self.dfs(i,j,grid1,grid2):\n",
    "                        cnt+=1\n",
    "        return cnt\n",
    "    def dfs(self, x, y,grid1,grid2):\n",
    "        dx = [-1,0,1,0]\n",
    "        dy = [0,1,0,-1]\n",
    "        grid2[x][y] = 0\n",
    "        flag = True\n",
    "        if grid1[x][y] == 0: flag = False\n",
    "        for i in range(4):\n",
    "            a = x+dx[i]\n",
    "            b = y +dy[i]\n",
    "            if a >=0 and a < len(grid1) and b>=0 and b<len(grid1[0]) and grid2[a][b]:\n",
    "                if not self.dfs(a, b, grid1,grid2):\n",
    "                    flag = False\n",
    "        return flag\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        self.grid1=grid1\n",
    "        self.grid2=grid2\n",
    "        ans=0\n",
    "        self.visited=set()\n",
    "        self.m=m=len(grid1)\n",
    "        self.n=n=len(grid1[0])\n",
    "        self.flag=True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==1 and not (i,j) in self.visited:\n",
    "                    self.dfs((i,j))\n",
    "                    if self.flag:\n",
    "                        ans+=1\n",
    "                    self.flag=True\n",
    "        return ans\n",
    "    \n",
    "    \n",
    "    def dfs(self, loc):\n",
    "        self.visited.add(loc)\n",
    "        x,y=loc\n",
    "        if self.grid1[x][y]==0:\n",
    "            self.flag=False\n",
    "        direct=[(-1,0),(0,1),(1,0),(0,-1)]\n",
    "        for dx,dy in direct:\n",
    "            newx=x+dx\n",
    "            newy=y+dy\n",
    "            if 0<=newx<self.m and 0<=newy<self.n and self.grid2[newx][newy]==1 and not (newx, newy) in self.visited:\n",
    "                self.dfs((newx, newy))\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    isOverriding = 1\n",
    "    def dfs(self, grid1, grid2, flag, r, c):\n",
    "        if 0 == grid1[r][c]:\n",
    "            self.isOverriding = 0\n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        for k in range(4):\n",
    "            y = r + dy[k]\n",
    "            x = c + dx[k]\n",
    "            if y >= 0 and y < len(grid1) and x >= 0 and x < len(grid1[0]) and 0 == flag[y][x] and 1 == grid2[y][x]:\n",
    "                flag[y][x] = 1\n",
    "                self.dfs(grid1, grid2, flag, y, x)\n",
    " \n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "        ans = 0\n",
    "        flag = [[0 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if 1 == grid2[i][j] and 0 == flag[i][j]:\n",
    "                    flag[i][j] = 1\n",
    "                    self.dfs(grid1, grid2, flag, i, j)\n",
    "                    ans += self.isOverriding\n",
    "                    self.isOverriding = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        rows, cols = len(grid2), len(grid2[0])\n",
    "        self.path_set = set()\n",
    "        count = 0\n",
    "\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                if grid2[row][col] == 1 and (row, col) not in self.path_set:\n",
    "                    if self.is_sub_island(grid1, grid2, row, col):\n",
    "                        count += 1\n",
    "                    # print(row, col, count)\n",
    "                    # print(self.path_set)\n",
    "        \n",
    "        return count\n",
    "    \n",
    "    def is_sub_island(self, grid1, grid2, row: int, col: int) -> bool:\n",
    "        rows, cols = len(grid2), len(grid2[0])\n",
    "        is_sub = True\n",
    "\n",
    "        if (row, col) in self.path_set:\n",
    "            return True\n",
    "        self.path_set.add((row, col))\n",
    "\n",
    "        # 如果 grid2 为 1 的位置，grid1 不为 1，则说明当前岛屿不为 grid1 的子岛屿\n",
    "        if grid1[row][col] != 1:\n",
    "            is_sub = False\n",
    "        \n",
    "        for dire in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n",
    "            new_row, new_col = row + dire[0], col + dire[1]\n",
    "\n",
    "            if 0 <= new_row < rows and 0 <= new_col < cols and (new_row, new_col) not in self.path_set and grid2[new_row][new_col] == 1:\n",
    "                is_sub = is_sub & self.is_sub_island(grid1, grid2, new_row, new_col)\n",
    "        \n",
    "        return is_sub\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m = len(grid1)\n",
    "        n = len(grid1[0])\n",
    "        num_sub_island = 0\n",
    "        \n",
    "        # dfs traverse a island starting from (i, j) and turn it into water\n",
    "        def flood_fill(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return\n",
    "            if grid2[i][j] == 0:\n",
    "                return           \n",
    "            grid2[i][j] = 0\n",
    "            for (x, y) in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:\n",
    "                flood_fill(x, y)           \n",
    "            \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0:\n",
    "                    flood_fill(i, j)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    num_sub_island += 1\n",
    "                    flood_fill(i, j)\n",
    "        \n",
    "        return num_sub_island"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        for i in range(len(grid2)):\n",
    "            for j in range(len(grid2[0])):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    self.dfs(grid2, i, j)\n",
    "        count = 0\n",
    "        for i in range(len(grid2)):\n",
    "            for j in range(len(grid2[0])):\n",
    "                if grid2[i][j] == 1:\n",
    "                    self.dfs(grid2, i, j)\n",
    "                    count += 1\n",
    "        return count\n",
    "                    \n",
    "    def dfs(self, grid, i, j):\n",
    "        if i < 0 or j < 0 or i > len(grid) - 1 or j > len(grid[0]) - 1 or grid[i][j] == 0:\n",
    "            return\n",
    "        grid[i][j] = 0\n",
    "        for m, n in [(i, j+1), (i, j-1), (i+1, j), (i-1, j)]:\n",
    "            self.dfs(grid, m, n)           \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        def dfs(grid:List[List[int]], i:int, j:int):\n",
    "            if not 0<=i<m or not 0<=j<n or grid[i][j] == 0:\n",
    "                return\n",
    "            grid[i][j] = 0\n",
    "            for i_next, j_next in [(i,j+1),(i,j-1),(i-1,j),(i+1,j)]:\n",
    "                dfs(grid, i_next,j_next)\n",
    "        \n",
    "        m,n = len(grid1), len(grid1[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid1[i][j] == 0 and grid2[i][j] == 1:\n",
    "                    dfs(grid2, i, j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    res += 1\n",
    "                    dfs(grid2, i, j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        n,m,counter=len(grid2),len(grid2[0]),0\n",
    "        def dfs_count(i:int,j:int)->bool:\n",
    "            grid2[i][j]=0\n",
    "            ret=bool(grid1[i][j])\n",
    "            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if x in range(n) and y in range(m):\n",
    "                    if grid2[x][y]:\n",
    "                        ret=dfs_count(x,y) and ret\n",
    "            return ret\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid2[i][j]:\n",
    "                    counter+=int(dfs_count(i,j))\n",
    "        return counter\n",
    "        # m, n = len(grid1), len(grid1[0])\n",
    "\n",
    "        # def bfs(sx: int, sy: int) -> int:\n",
    "        #     q = deque([(sx, sy)])\n",
    "        #     grid2[sx][sy] = 0\n",
    "        #     # 判断岛屿包含的每一个格子是否都在 grid1 中出现了\n",
    "        #     check = (grid1[sx][sy] == 1)\n",
    "        #     while q:\n",
    "        #         x, y = q.popleft()\n",
    "        #         for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "        #             if 0 <= nx < m and 0 <= ny < n and grid2[nx][ny] == 1:\n",
    "        #                 q.append((nx, ny))\n",
    "        #                 grid2[nx][ny] = 0\n",
    "        #                 if grid1[nx][ny] != 1:\n",
    "        #                     check = False\n",
    "            \n",
    "        #     return int(check)\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid2[i][j] == 1:\n",
    "        #             ans += bfs(i, j)\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        #BFS,对grid2搜索，如果有岛屿的地方，grid1也有岛屿则说明是子岛屿；否则grid2有岛屿但grid1无，则返回False\n",
    "        def dfs(grid2, i, j):\n",
    "            nonlocal flag\n",
    "            grid2[i][j] = 0\n",
    "            if grid1[i][j] == 0:\n",
    "                flag = False\n",
    "            for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                if 0 <= x < len(grid2) and 0 <= y < len(grid2[0])and grid2[x][y] == 1:\n",
    "                    dfs(grid2, x, y)\n",
    "        if not grid1 or not grid2:\n",
    "            return 0\n",
    "        m, n = len(grid1), len(grid1[0])\n",
    "        res = 0\n",
    "        flag = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j] == 1:\n",
    "                    flag = True\n",
    "                    dfs(grid2, i, j)\n",
    "                    if flag:\n",
    "                      res += 1\n",
    "        # print(grid1, grid2)\n",
    "        return res\n",
    "    \n",
    "        #BFS\n",
    "        # def bfs(grid2, i, j):\n",
    "        #     grid2[i][j] = 0\n",
    "        #     deque = collections.deque([(i, j)])\n",
    "        #     temp = (grid1[i][j] == 1)\n",
    "        #     while deque:\n",
    "        #         i, j = deque.popleft()\n",
    "        #         for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "        #             if 0 <= x < len(grid2) and 0 <= y < len(grid2[0]) and grid2[x][y] == 1:\n",
    "        #                 deque.append((x, y))\n",
    "        #                 grid2[x][y] = 0\n",
    "        #                 if grid1[x][y] != 1:\n",
    "        #                     temp =  False\n",
    "        #     return temp\n",
    "        # if not grid1 or not grid2:\n",
    "        #     return 0\n",
    "        # m, n = len(grid1), len(grid1[0])\n",
    "        # res = 0\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid2[i][j] == 1:\n",
    "        #             if bfs(grid2, i, j):\n",
    "        #                 res += 1\n",
    "        # # print(grid1, grid2)\n",
    "        # return res\n",
    "    \n",
    "      # #DFS,两个grid同时进行，如果都为1才继续， 未AC，8/\n",
    "      # def dfs(grid1, grid2, i, j):\n",
    "      #     if 0 <= i < len(grid1) and 0 <= j < len(grid1[0]):\n",
    "      #         if grid2[i][j] == 1 and grid1[i][j] != 1:\n",
    "      #             return False\n",
    "          \n",
    "      #     grid1[i][j] = grid2[i][j] = 0\n",
    "      #     temp = True\n",
    "      #     for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "      #         if 0 <= x < len(grid1) and 0 <= y < len(grid1[0]) and grid2[x][y] == 1 and grid1[x][y] == 0:\n",
    "      #             return False\n",
    "      #         if 0 <= x < len(grid1) and 0 <= y < len(grid1[0]) and grid2[x][y] == 1 and grid1[x][y] == 1:\n",
    "      #             temp = dfs(grid1, grid2, x, y)\n",
    "      #     return temp\n",
    "      # if not grid1 or not grid2:\n",
    "      #     return 0\n",
    "      # m, n = len(grid1), len(grid1[0])\n",
    "      # res = 0\n",
    "      # for i in range(m):\n",
    "      #     for j in range(n):\n",
    "      #         if grid2[i][j] == 1 and grid1[i][j] == 1:\n",
    "      #             if dfs(grid1, grid2, i, j):\n",
    "      #               res += 1\n",
    "      # # print(grid1, grid2)\n",
    "      # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        m=len(grid1)\n",
    "        n=len(grid1[0])\n",
    "        #uf1=UnionFind(m*n+1)\n",
    "        uf2=UnionFind(m*n+1)\n",
    "        #island1=[]\n",
    "        island2=[]\n",
    "        res=0\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid1[i][j]==0:\n",
    "        #             uf1.union(i*n+j,m*n)\n",
    "        #             continue\n",
    "        #         if i<m-1 and grid1[i+1][j] == 1:\n",
    "        #             uf1.union(i*n+j,(i+1)*n+j)\n",
    "        #         if j<n-1 and grid1[i][j+1] == 1:\n",
    "        #             uf1.union(i*n+j,i*n+j+1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid2[i][j]==0:\n",
    "                    uf2.union(i*n+j,m*n)\n",
    "                    continue\n",
    "                if i<m-1 and grid2[i+1][j] == 1:\n",
    "                    uf2.union(i*n+j,(i+1)*n+j)\n",
    "                if j<n-1 and grid2[i][j+1] == 1:\n",
    "                    uf2.union(i*n+j,i*n+j+1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # if uf1.find(i*n+j)==i*n+j:\n",
    "                #     island1.append(i*n+j)\n",
    "                if uf2.find(i*n+j)==i*n+j:\n",
    "                    island2.append(i*n+j)\n",
    "    \n",
    "\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if uf2.find(i*n+j)==i*n+j:\n",
    "        #             island2.append(i*n+j)\n",
    "\n",
    "        # for a in island2:\n",
    "        #     for b in island1:\n",
    "        #         if uf2.child[a].issubset(uf1.child[b]):\n",
    "        #             res+=1\n",
    "\n",
    "        \n",
    "\n",
    "        # print(island1)\n",
    "        for a in island2:\n",
    "            cur=1\n",
    "            for loc in uf2.child[a]:\n",
    "                i=loc//n\n",
    "                j=loc%n\n",
    "                if grid1[i][j]==0:\n",
    "                    cur*=0\n",
    "            res+=cur\n",
    "\n",
    "        # for b in island1:\n",
    "        #     print(uf1.child[b])\n",
    "        #print(island2)\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.father=[i for i in range(n)]\n",
    "        self.size=[1 for i in range(n)]\n",
    "        self.child=[set([i]) for i in range(n)]\n",
    "\n",
    "    def find(self,a):\n",
    "        if self.father[a] != a:\n",
    "            self.father[a]=self.find(self.father[a])\n",
    "        return self.father[a]\n",
    "\n",
    "    def union(self,a,b):\n",
    "        fa,fb=self.find(a),self.find(b)\n",
    "        if fa == fb:\n",
    "            return\n",
    "        if self.size[fa]>self.size[fb]:\n",
    "            self.father[fb]=fa\n",
    "            self.size[fa]+=self.size[fb]\n",
    "            self.child[fa].update(self.child[fb])\n",
    "        else:\n",
    "            self.father[fa]=fb\n",
    "            self.size[fb]+=self.size[fa]\n",
    "            self.child[fb].update(self.child[fa])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid2)\n",
    "        n = len(grid2[0])\n",
    "        def dfs(i, j):\n",
    "            grid2[i][j] = 0\n",
    "            flag = grid1[i][j]\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if -1<x<m and -1<y<n and grid2[x][y]:\n",
    "                    flag &= dfs(x, y)\n",
    "            return flag\n",
    "\n",
    "        return sum(grid2[i][j] and dfs(i, j) for i in range(m) for j in range(n))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
